package lc.q1_50;

/**
 * 给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 '?' 和 '*' 的通配符匹配。
 *
 * '?' 可以匹配任何单个字符。
 * '*' 可以匹配任意字符串（包括空字符串）。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/wildcard-matching
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Q44 {

    public boolean isMatch(String s, String p) {
        p = p.replaceAll("\\*+", "*");
        return _match(s, p);
    }

    private boolean _match(String s, String p ) {
        // 这种方案会超时
        // 动态递归：找出归纳特征
        // 调整，dp[i][j]与dp[i-1][j-1]
        boolean[][] dp = new boolean[s.length()+1][];
        for (int i = 0; i < s.length()+1; i++) {
            dp[i] = new boolean[p.length()+1];
        }
        dp[0][0] = true;

        for (int j = 0; j < p.length(); j++) {
            // 内外循环如何处理最佳
            if (p.charAt(j)=='*') {
                for (int i = 0; i < s.length()+1; i++) {
                    if (dp[i][j]) {
                        for (int k = i; k < s.length()+1; k++) {
                            dp[k][j+1] = true;
                        }
                    }
                }
            } else {
                for (int i = 0; i < s.length(); i++) {
                    if (s.charAt(i) == p.charAt(j) || p.charAt(j)=='?') {
                        dp[i+1][j+1] = dp[i][j];
                    }
                }
            }


        }

        return dp[s.length()][p.length()];
    }

    public static void main(String[] args) {
        String[] sp = new String[]{"",
        "*"};
        System.out.println(new Q44().isMatch(sp[0], sp[1]));
    }

}
